/**
 * @brief 点差分实现
 */
class PointDifference : public LCATree {
public:
    using LCATree::LCATree;

    void applyUpdate(int u, int v, i64 data) override {
        const int ancester = lca(u, v);
        diff[u] += data;
        diff[v] += data;
        diff[ancester] -= data;
        if(up[ancester][0] != ancester) {
            diff[up[ancester][0]] -= data;
        }
    }
    
    void calculateResult() override {
        postOrderCalculate(root, root);
    }
private:
    void postOrderCalculate(int u, int fa) {
        for(auto v : adj[u]) {
            if(v == fa) {
                continue;
            }
            postOrderCaculate(v, u);
            diff[u] += diff[v];
        }
    }
};